{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Coin Bonus"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #binary-indexed-tree #segment-tree #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树状数组 #线段树 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: bonus"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #发 LeetCoin"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>力扣决定给一个刷题团队发<code>LeetCoin</code>作为奖励。同时，为了监控给大家发了多少<code>LeetCoin</code>，力扣有时候也会进行查询。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>该刷题团队的管理模式可以用一棵树表示：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>团队只有一个负责人，编号为1。除了该负责人外，每个人有且仅有一个领导（负责人没有领导）；</li>\n",
    "\t<li>不存在循环管理的情况，如A管理B，B管理C，C管理A。</li>\n",
    "</ol>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>力扣想进行的操作有以下三种：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>给团队的一个成员（也可以是负责人）发一定数量的<code>LeetCoin</code>；</li>\n",
    "\t<li>给团队的一个成员（也可以是负责人），以及他/她管理的所有人（即他/她的下属、他/她下属的下属，&hellip;&hellip;），发一定数量的<code>LeetCoin</code>；</li>\n",
    "\t<li>查询某一个成员（也可以是负责人），以及他/她管理的所有人被发到的<code>LeetCoin</code>之和。</li>\n",
    "</ol>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>输入：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>N</code>表示团队成员的个数（编号为1～N，负责人为1）；</li>\n",
    "\t<li><code>leadership</code>是大小为<code>(N&nbsp;- 1) * 2</code>的二维数组，其中每个元素<code>[a, b]</code>代表<code>b</code>是<code>a</code>的下属；</li>\n",
    "\t<li><code>operations</code>是一个长度为<code>Q</code>的二维数组，代表以时间排序的操作，格式如下：\n",
    "\t<ol>\n",
    "\t\t<li><code>operations[i][0] = 1</code>: 代表第一种操作，<code>operations[i][1]</code>代表成员的编号，<code>operations[i][2]</code>代表<code>LeetCoin</code>的数量；</li>\n",
    "\t\t<li><code>operations[i][0] = 2</code>: 代表第二种操作，<code>operations[i][1]</code>代表成员的编号，<code>operations[i][2]</code>代表<code>LeetCoin</code>的数量；</li>\n",
    "\t\t<li><code>operations[i][0] = 3</code>: 代表第三种操作，<code>operations[i][1]</code>代表成员的编号；</li>\n",
    "\t</ol>\n",
    "\t</li>\n",
    "</ol>\n",
    "\n",
    "<p><strong>输出：</strong></p>\n",
    "\n",
    "<p>返回一个数组，数组里是每次<strong>查询</strong>的返回值（发<code>LeetCoin</code>的操作不需要任何返回值）。由于发的<code>LeetCoin</code>很多，请把每次查询的结果模<code>1e9+7 (1000000007)</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>N = 6, leadership = [[1, 2], [1, 6], [2, 3], [2, 5], [1, 4]], operations = [[1, 1, 500], [2, 2, 50], [3, 1], [2, 6, 15], [3, 1]]\n",
    "<strong>输出：</strong>[650, 665]\n",
    "<strong>解释：</strong>团队的管理关系见下图。\n",
    "第一次查询时，每个成员得到的LeetCoin的数量分别为（按编号顺序）：500, 50, 50, 0, 50, 0;\n",
    "第二次查询时，每个成员得到的LeetCoin的数量分别为（按编号顺序）：500, 50, 50, 0, 50, 15.\n",
    "</pre>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/09/09/coin_example_1.jpg\" style=\"height: 344px; width: 300px;\"></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>限制：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>1 &lt;= N &lt;= 50000</code></li>\n",
    "\t<li><code>1 &lt;= Q &lt;= 50000</code></li>\n",
    "\t<li><code>operations[i][0] != 3 时，1 &lt;= operations[i][2]&nbsp;&lt;= 5000</code></li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [coin-bonus](https://leetcode.cn/problems/coin-bonus/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [coin-bonus](https://leetcode.cn/problems/coin-bonus/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['6\\n[[1, 2], [1, 6], [2, 3], [2, 5], [1, 4]]\\n[[1, 1, 500], [2, 2, 50], [3, 1], [2, 6, 15], [3, 1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class HLD:\n",
    "    def __init__(self, g, root): \n",
    "        #无论是点还是dfn还是dep，都从1开始，默认0是无\n",
    "        n=len(g)\n",
    "        self.g=g\n",
    "        self.fa=[0]*(n+5)   #父节点，0表示无父节点\n",
    "        self.size=[1]*(n+5) #子树大小\n",
    "        self.dep=[0]*(n+5)  #深度，根深度为1\n",
    "        self.son=[0]*(n+5)  #重儿子，0表示无儿子\n",
    "        self.dfn=[0]*(n+5)  #dfs序，子树终点的dfs序是dfn[i]+size[i]-1\n",
    "        self.top=[0]*(n+5)  #所在重链起点，起点就是自己\n",
    "        self.rank=[0]*(n+5) #dfs序为i的节点编号\n",
    "\n",
    "        fa=self.fa;size=self.size;dep=self.dep;son=self.son\n",
    "        dfn=self.dfn;top=self.top;rank=self.rank\n",
    "        stk=[[root,0,0]] #node,flag,fa\n",
    "        dep[root]=1\n",
    "        while stk:\n",
    "            u,flag,father=stk.pop()\n",
    "            if flag:\n",
    "                for v in g[u]:\n",
    "                    if v!=father:\n",
    "                        size[u]+=size[v]\n",
    "                        if son[u]==0 or size[v]>size[son[u]]:\n",
    "                            son[u]=v\n",
    "            else:\n",
    "                stk.append([u,1,father])\n",
    "                for v in g[u]:\n",
    "                    if v!=father:\n",
    "                        stk.append([v,0,u])\n",
    "                        fa[v]=u\n",
    "                        dep[v]=dep[u]+1\n",
    "        stk=[[root,root]]\n",
    "        tot=1\n",
    "        while stk:\n",
    "            u,tops=stk.pop()\n",
    "            dfn[u]=tot\n",
    "            tot+=1\n",
    "            top[u]=tops\n",
    "            if son[u]==0:\n",
    "                continue\n",
    "            for v in g[u]:\n",
    "                if v!=fa[u] and v!=son[u]:\n",
    "                    stk.append([v,v])\n",
    "            stk.append([son[u],tops])\n",
    "mod=10**9+7\n",
    "class BIT2:\n",
    "    \"\"\"区间更新，区间和查询 \"\"\"  \n",
    "    __slots__ = \"size\", \"_tree1\", \"_tree2\"\n",
    "    def __init__(self, n: int):\n",
    "        self.size = n\n",
    "        self._tree1 = [0]*(n+1)\n",
    "        self._tree2 = [0]*(n+1)\n",
    "\n",
    "    def add(self, left: int, right: int, delta: int) -> None:\n",
    "        \"\"\"闭区间[left, right]加delta\"\"\"\n",
    "        self._add(left, delta)\n",
    "        self._add(right + 1, -delta)\n",
    "\n",
    "    def query(self, left: int, right: int) -> int:\n",
    "        \"\"\"闭区间[left, right]的和\"\"\"\n",
    "        return (self._query(right) - self._query(left - 1))%mod\n",
    "\n",
    "    def _add(self, index: int, delta: int) -> None:\n",
    "        rawIndex = index\n",
    "        while index <= self.size:\n",
    "            self._tree1[index] += delta\n",
    "            self._tree1[index]%=mod\n",
    "            self._tree2[index] += (rawIndex - 1) * delta\n",
    "            self._tree2[index]%=mod\n",
    "            index += index & -index\n",
    "\n",
    "    def _query(self, index: int) -> int:\n",
    "        if index > self.size:\n",
    "            index = self.size\n",
    "        rawIndex = index\n",
    "        res = 0\n",
    "        while index > 0:\n",
    "            res += rawIndex * self._tree1[index] - self._tree2[index]\n",
    "            res%=mod\n",
    "            index -= index & -index\n",
    "        return res\n",
    "class Solution:\n",
    "    def bonus(self, n: int, leadership: List[List[int]], operations: List[List[int]]) -> List[int]:\n",
    "        g=[[] for _ in range(n+1)]\n",
    "        for u,v in leadership:\n",
    "            g[u]+=[v]\n",
    "            g[v]+=[u]\n",
    "        hld=HLD(g,1)\n",
    "        dfn=hld.dfn\n",
    "        size=hld.size\n",
    "        bit=BIT2(n+10)\n",
    "        res=[]\n",
    "        for op in operations:\n",
    "            if op[0]==1:\n",
    "                u=op[1]\n",
    "                x=op[2]\n",
    "                bit.add(dfn[u],dfn[u],x)\n",
    "            elif op[0]==2:\n",
    "                u=op[1]\n",
    "                x=op[2]\n",
    "                bit.add(dfn[u],dfn[u]+size[u]-1,x)\n",
    "            else:\n",
    "                u=op[1]\n",
    "                res.append(bit.query(dfn[u],dfn[u]+size[u]-1))\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = int(1e9 + 7)\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.n = n + 5\n",
    "        self.sum = [0 for _ in range(n + 10)]\n",
    "        self.ntimessum = [0 for _ in range(n + 10)]\n",
    "    \n",
    "    def lowbit(self, x):\n",
    "        return x & (-x)\n",
    "\n",
    "    # 在 pos 位置加上 k\n",
    "    def update(self, pos, k):\n",
    "        x = pos\n",
    "        while pos <= self.n:\n",
    "            self.sum[pos] += k\n",
    "            self.sum[pos] %= M\n",
    "            self.ntimessum[pos] += k * (x - 1)\n",
    "            self.ntimessum[pos] %= M\n",
    "            pos += self.lowbit(pos)\n",
    "    \n",
    "    # 区间更新 + 单点查询\n",
    "    def askis(self, pos):\n",
    "        if not pos:\n",
    "            return 0\n",
    "        ret = 0\n",
    "        while pos:\n",
    "            ret += self.sum[pos]\n",
    "            ret %= M\n",
    "            pos -= lowbit(pos)\n",
    "        return ret\n",
    "    \n",
    "    # 单点更新 + 区间查询\n",
    "    def asksi(self, l, r):\n",
    "        if l > r:\n",
    "            return 0\n",
    "        return askis(r) - askis(l - 1)\n",
    "    \n",
    "    # 单点更新 + 单点查询\n",
    "    def askss(self, pos):\n",
    "        return askis(pos) - askis(pos - 1)\n",
    "    \n",
    "    # 区间更新 + 区间查询\n",
    "    def askii(self, pos):\n",
    "        if not pos:\n",
    "            return 0\n",
    "        ret = 0\n",
    "        x = pos\n",
    "        while pos:\n",
    "            ret += x * self.sum[pos] - self.ntimessum[pos]\n",
    "            ret %= M\n",
    "            pos -= self.lowbit(pos)\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def bonus(self, n: int, leadership: List[List[int]], operations: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        # 邻接表\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        begin = [0 for _ in range(n + 1)]\n",
    "        end = [0 for _ in range(n + 1)]\n",
    "        id = 1\n",
    "\n",
    "        for l in leadership:\n",
    "            g[l[0]].append(l[1])\n",
    "        \n",
    "        # 深搜\n",
    "        def dfs(cur):\n",
    "            nonlocal id\n",
    "            begin[cur] = id\n",
    "            for child in g[cur]:\n",
    "                dfs(child)\n",
    "            end[cur] = id\n",
    "            id += 1\n",
    "        dfs(1)\n",
    "        \n",
    "        # 树状数组\n",
    "        b = BIT(n)\n",
    "        ret = []\n",
    "        for q in operations:\n",
    "            if q[0] == 1:\n",
    "                b.update(end[q[1]], q[2])\n",
    "                b.update(end[q[1]] + 1, -q[2])\n",
    "            elif q[0] == 2:\n",
    "                b.update(begin[q[1]], q[2])\n",
    "                b.update(end[q[1]] + 1, -q[2])\n",
    "            else:\n",
    "                ans = b.askii(end[q[1]]) - b.askii(begin[q[1]] - 1)\n",
    "                ret.append((ans % M + M) % M)\n",
    "\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = int(1e9 + 7)\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.n = n + 5\n",
    "        self.sum = [0 for _ in range(n + 10)]\n",
    "        self.ntimessum = [0 for _ in range(n + 10)]\n",
    "    \n",
    "    def lowbit(self, x):\n",
    "        return x & (-x)\n",
    "\n",
    "    # 在 pos 位置加上 k\n",
    "    def update(self, pos, k):\n",
    "        x = pos\n",
    "        while pos <= self.n:\n",
    "            self.sum[pos] += k\n",
    "            self.sum[pos] %= M\n",
    "            self.ntimessum[pos] += k * (x - 1)\n",
    "            self.ntimessum[pos] %= M\n",
    "            pos += self.lowbit(pos)\n",
    "    \n",
    "    # 区间更新 + 单点查询\n",
    "    def askis(self, pos):\n",
    "        if not pos:\n",
    "            return 0\n",
    "        ret = 0\n",
    "        while pos:\n",
    "            ret += self.sum[pos]\n",
    "            ret %= M\n",
    "            pos -= lowbit(pos)\n",
    "        return ret\n",
    "    \n",
    "    # 单点更新 + 区间查询\n",
    "    def asksi(self, l, r):\n",
    "        if l > r:\n",
    "            return 0\n",
    "        return askis(r) - askis(l - 1)\n",
    "    \n",
    "    # 单点更新 + 单点查询\n",
    "    def askss(self, pos):\n",
    "        return askis(pos) - askis(pos - 1)\n",
    "    \n",
    "    # 区间更新 + 区间查询\n",
    "    def askii(self, pos):\n",
    "        if not pos:\n",
    "            return 0\n",
    "        ret = 0\n",
    "        x = pos\n",
    "        while pos:\n",
    "            ret += x * self.sum[pos] - self.ntimessum[pos]\n",
    "            ret %= M\n",
    "            pos -= self.lowbit(pos)\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def bonus(self, n: int, leadership: List[List[int]], operations: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        # 邻接表\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        begin = [0 for _ in range(n + 1)]\n",
    "        end = [0 for _ in range(n + 1)]\n",
    "        id = 1\n",
    "\n",
    "        for l in leadership:\n",
    "            g[l[0]].append(l[1])\n",
    "        \n",
    "        # 深搜\n",
    "        def dfs(cur):\n",
    "            nonlocal id\n",
    "            begin[cur] = id\n",
    "            for child in g[cur]:\n",
    "                dfs(child)\n",
    "            end[cur] = id\n",
    "            id += 1\n",
    "        dfs(1)\n",
    "        \n",
    "        # 树状数组\n",
    "        b = BIT(n)\n",
    "        ret = []\n",
    "        for q in operations:\n",
    "            if q[0] == 1:\n",
    "                b.update(end[q[1]], q[2])\n",
    "                b.update(end[q[1]] + 1, -q[2])\n",
    "            elif q[0] == 2:\n",
    "                b.update(begin[q[1]], q[2])\n",
    "                b.update(end[q[1]] + 1, -q[2])\n",
    "            else:\n",
    "                ans = b.askii(end[q[1]]) - b.askii(begin[q[1]] - 1)\n",
    "                ret.append((ans % M + M) % M)\n",
    "\n",
    "        return ret\n",
    "\n",
    "\n",
    "                    \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = int(1e9 + 7)\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.n = n + 5\n",
    "        self.sum = [0 for _ in range(n + 10)]\n",
    "        self.ntimessum = [0 for _ in range(n + 10)]\n",
    "    \n",
    "    def lowbit(self, x):\n",
    "        return x & (-x)\n",
    "\n",
    "    # 在 pos 位置加上 k\n",
    "    def update(self, pos, k):\n",
    "        x = pos\n",
    "        while pos <= self.n:\n",
    "            self.sum[pos] += k\n",
    "            self.sum[pos] %= M\n",
    "            self.ntimessum[pos] += k * (x - 1)\n",
    "            self.ntimessum[pos] %= M\n",
    "            pos += self.lowbit(pos)\n",
    "    \n",
    "    # 区间更新 + 单点查询\n",
    "    def askis(self, pos):\n",
    "        if not pos:\n",
    "            return 0\n",
    "        ret = 0\n",
    "        while pos:\n",
    "            ret += self.sum[pos]\n",
    "            ret %= M\n",
    "            pos -= lowbit(pos)\n",
    "        return ret\n",
    "    \n",
    "    # 单点更新 + 区间查询\n",
    "    def asksi(self, l, r):\n",
    "        if l > r:\n",
    "            return 0\n",
    "        return askis(r) - askis(l - 1)\n",
    "    \n",
    "    # 单点更新 + 单点查询\n",
    "    def askss(self, pos):\n",
    "        return askis(pos) - askis(pos - 1)\n",
    "    \n",
    "    # 区间更新 + 区间查询\n",
    "    def askii(self, pos):\n",
    "        if not pos:\n",
    "            return 0\n",
    "        ret = 0\n",
    "        x = pos\n",
    "        while pos:\n",
    "            ret += x * self.sum[pos] - self.ntimessum[pos]\n",
    "            ret %= M\n",
    "            pos -= self.lowbit(pos)\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def bonus(self, n: int, leadership: List[List[int]], operations: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        # 邻接表\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        begin = [0 for _ in range(n + 1)]\n",
    "        end = [0 for _ in range(n + 1)]\n",
    "        id = 1\n",
    "\n",
    "        for l in leadership:\n",
    "            g[l[0]].append(l[1])\n",
    "        \n",
    "        # 深搜\n",
    "        def dfs(cur):\n",
    "            nonlocal id\n",
    "            begin[cur] = id\n",
    "            for child in g[cur]:\n",
    "                dfs(child)\n",
    "            end[cur] = id\n",
    "            id += 1\n",
    "        dfs(1)\n",
    "        \n",
    "        # 树状数组\n",
    "        b = BIT(n)\n",
    "        ret = []\n",
    "        for q in operations:\n",
    "            if q[0] == 1:\n",
    "                b.update(end[q[1]], q[2])\n",
    "                b.update(end[q[1]] + 1, -q[2])\n",
    "            elif q[0] == 2:\n",
    "                b.update(begin[q[1]], q[2])\n",
    "                b.update(end[q[1]] + 1, -q[2])\n",
    "            else:\n",
    "                ans = b.askii(end[q[1]]) - b.askii(begin[q[1]] - 1)\n",
    "                ret.append((ans % M + M) % M)\n",
    "\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bonus(self, n: int, leadership: List[List[int]], operations: List[List[int]]) -> List[int]:\n",
    "        mod = 1000000007\n",
    "\n",
    "        class BIT:\n",
    "\n",
    "            def __init__(self, MAXINDEX: int):\n",
    "                self.MAXINDEX = MAXINDEX\n",
    "\n",
    "                self.c1 = [0] * MAXINDEX\n",
    "                self.c2 = [0] * MAXINDEX\n",
    "\n",
    "\n",
    "            def _lowbit(self, a: int):\n",
    "                return a & (-a)\n",
    "\n",
    "            def _add(self, index: int, value: int):\n",
    "                x = index\n",
    "                while(index < self.MAXINDEX):\n",
    "                    self.c1[index] = (self.c1[index] + value) % mod\n",
    "                    self.c2[index] = (self.c2[index] + (x-1) * value) % mod\n",
    "                    index += self._lowbit(index)\n",
    "            \n",
    "            def add(self, l:int, r:int, value:int):\n",
    "                self._add(l, value)\n",
    "                self._add(r+1, -value)\n",
    "\n",
    "\n",
    "            def query(self, index:int) -> int:\n",
    "                res = 0\n",
    "                x = index\n",
    "                while(index):\n",
    "                    res += (self.c1[index] * x) % mod\n",
    "                    res -= self.c2[index] % mod\n",
    "                    index -= self._lowbit(index)\n",
    "                return res %  mod\n",
    "\n",
    "            def range_query(self, l:int, r:int) -> int:\n",
    "                return (-self.query(l-1) + self.query(r)) % mod\n",
    "    \n",
    "        #构建连接关系图\n",
    "        adj = [[] for i in range(n+1)]\n",
    "        for edge in leadership:\n",
    "            lead, empolyee = edge[0], edge[1]\n",
    "            empolyee_list = adj[lead]\n",
    "            empolyee_list.append(empolyee)\n",
    "            adj[lead] = empolyee_list\n",
    "        \n",
    "\n",
    "        begin_id = [1] * (n+1) #记录某个点控制范围的起点\n",
    "        end_id = [1] * (n+1) #记录某个点控制范围的终点，也是自己的坐标\n",
    "\n",
    "        def dfs(index: int, _id: int) -> int:\n",
    "            begin_id[index] = _id\n",
    "\n",
    "            nb = adj[index]\n",
    "            if not nb:\n",
    "                end_id[index] = _id\n",
    "                return _id\n",
    "            \n",
    "            next_id = _id \n",
    "            end_id[index] = next_id\n",
    "            for n in nb:\n",
    "                next_id = dfs(n, next_id) + 1\n",
    "                end_id[index] = next_id\n",
    "            return next_id\n",
    "        \n",
    "        dfs(1, 1)\n",
    "        bit = BIT(n+1)\n",
    "        res = []\n",
    "\n",
    "        for op in operations:\n",
    "            match op[0]:\n",
    "                case 1:\n",
    "                    index, value = op[1], op[2]\n",
    "                    l, r = end_id[index], end_id[index]\n",
    "                    bit.add(l, r, value)\n",
    "                case 2:\n",
    "                    index, value = op[1], op[2]\n",
    "                    l, r = begin_id[index], end_id[index]\n",
    "                    bit.add(l, r, value)\n",
    "                case 3:\n",
    "                    index = op[1]\n",
    "                    l, r = begin_id[index], end_id[index]\n",
    "                    res.append(bit.range_query(l, r))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    __slot__ = 'val', 'left', 'right', 'lazy', 'max'\n",
    "    def __init__(self, val=0, lazy=0, left=None, right=None) -> None:\n",
    "        self.val = val \n",
    "        self.left = left \n",
    "        self.right = right \n",
    "        self.lazy = lazy\n",
    "\n",
    "\n",
    "class SegTree:\n",
    "    def __init__(self, val=0, start=-10**9, end=10**9 ) -> None:\n",
    "        self.root = Node(val=val)\n",
    "        self.start = start\n",
    "        self.end = end \n",
    "      \n",
    "    def update(self, l, r, val):\n",
    "        def _update(start=self.start, end=self.end, node=self.root):\n",
    "            if not node:\n",
    "                node = self.root\n",
    "            if l <= start and end <= r:\n",
    "                node.val += (end - start + 1) * val\n",
    "                node.lazy += val\n",
    "                return \n",
    "            \n",
    "            mid = math.floor((start + end) / 2)\n",
    "            self.pushDown(node, mid - start + 1, end - mid)\n",
    "            if l <= mid:\n",
    "                _update(start, mid, node.left)\n",
    "            if r > mid:\n",
    "                _update(mid + 1, end, node.right)\n",
    "            self.pushUp(node)\n",
    "        _update()\n",
    "        \n",
    "\n",
    "    def query(self, l, r):\n",
    "        def _query(node=self.root, start=self.start, end=self.end): #max\n",
    "            if l <= start and end <= r:\n",
    "                return node.val\n",
    "            mid = math.floor((start + end) / 2) \n",
    "            ans = 0\n",
    "            self.pushDown(node, mid - start + 1, end - mid)\n",
    "            if l <= mid: \n",
    "                ans += _query(node.left, start, mid)\n",
    "            if r > mid: \n",
    "                ans += _query(node.right, mid + 1, end)\n",
    "            return ans \n",
    "\n",
    "        return _query()\n",
    "\n",
    "    def pushDown(self, node, leftNum, rightNum):\n",
    "        if node.left == None:\n",
    "            node.left = Node()\n",
    "        if node.right == None: \n",
    "            node.right = Node()\n",
    "        if node.lazy == 0:\n",
    "            return\n",
    "        node.left.val += node.lazy * leftNum\n",
    "        node.right.val += node.lazy * rightNum\n",
    "        # 对区间进行「加减」的更新操作，下推懒惰标记时需要累加起来，不能直接覆盖\n",
    "        node.left.lazy += node.lazy\n",
    "        node.right.lazy += node.lazy\n",
    "\n",
    "        node.lazy = 0\n",
    "\n",
    "    def pushUp(self, node):\n",
    "        node.val = node.left.val + node.right.val\n",
    "  \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def bonus(self, n: int, leadership: List[List[int]], operations: List[List[int]]):\n",
    "        seg = SegTree(0, 1, n)\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        begin = [0 for _ in range(n + 1)]\n",
    "        end = [0 for _ in range(n + 1)]\n",
    "        id = 0\n",
    "\n",
    "        for l in leadership:\n",
    "            g[l[0]].append(l[1])\n",
    "        \n",
    "        # 深搜\n",
    "        def dfs(cur):\n",
    "            nonlocal id\n",
    "            id += 1\n",
    "            begin[cur] = id\n",
    "            for child in g[cur]:\n",
    "                dfs(child)\n",
    "            end[cur] = id\n",
    "        dfs(1)\n",
    "\n",
    "        ans = []\n",
    "        for o in operations:\n",
    "            if o[0] == 1:\n",
    "                seg.update(begin[o[1]], begin[o[1]], o[2])\n",
    "            if o[0] == 2:\n",
    "                seg.update(begin[o[1]], end[o[1]], o[2])\n",
    "            if o[0] == 3:\n",
    "                ans.append(seg.query(begin[o[1]], end[o[1]])%1000000007)\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    __slot__ = 'val', 'left', 'right', 'lazy', 'max'\n",
    "    def __init__(self, val=0, lazy=0, left=None, right=None) -> None:\n",
    "        self.val = val \n",
    "        self.left = left \n",
    "        self.right = right \n",
    "        self.lazy = lazy\n",
    "\n",
    "\n",
    "class SegTree:\n",
    "    def __init__(self, val=0, start=-10**9, end=10**9 ) -> None:\n",
    "        self.root = Node(val=val)\n",
    "        self.start = start\n",
    "        self.end = end \n",
    "      \n",
    "    def update(self, l, r, val):\n",
    "        def _update(start=self.start, end=self.end, node=self.root):\n",
    "            if not node:\n",
    "                node = self.root\n",
    "            if l <= start and end <= r:\n",
    "                node.val += (end - start + 1) * val\n",
    "                node.lazy += val\n",
    "                return \n",
    "            \n",
    "            mid = math.floor((start + end) / 2)\n",
    "            self.pushDown(node, mid - start + 1, end - mid)\n",
    "            if l <= mid:\n",
    "                _update(start, mid, node.left)\n",
    "            if r > mid:\n",
    "                _update(mid + 1, end, node.right)\n",
    "            self.pushUp(node)\n",
    "        _update()\n",
    "        \n",
    "\n",
    "    def query(self, l, r):\n",
    "        def _query(node=self.root, start=self.start, end=self.end): #max\n",
    "            if l <= start and end <= r:\n",
    "                return node.val\n",
    "            mid = math.floor((start + end) / 2) \n",
    "            ans = 0\n",
    "            self.pushDown(node, mid - start + 1, end - mid)\n",
    "            if l <= mid: \n",
    "                ans += _query(node.left, start, mid)\n",
    "            if r > mid: \n",
    "                ans += _query(node.right, mid + 1, end)\n",
    "            return ans \n",
    "\n",
    "        return _query()\n",
    "\n",
    "    def pushDown(self, node, leftNum, rightNum):\n",
    "        if node.left == None:\n",
    "            node.left = Node()\n",
    "        if node.right == None: \n",
    "            node.right = Node()\n",
    "        if node.lazy == 0:\n",
    "            return\n",
    "        node.left.val += node.lazy * leftNum\n",
    "        node.right.val += node.lazy * rightNum\n",
    "        # 对区间进行「加减」的更新操作，下推懒惰标记时需要累加起来，不能直接覆盖\n",
    "        node.left.lazy += node.lazy\n",
    "        node.right.lazy += node.lazy\n",
    "\n",
    "        node.lazy = 0\n",
    "\n",
    "    def pushUp(self, node):\n",
    "        node.val = node.left.val + node.right.val\n",
    "  \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def bonus(self, n: int, leadership: List[List[int]], operations: List[List[int]]):\n",
    "        seg = SegTree(0, 1, n)\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        begin = [0 for _ in range(n + 1)]\n",
    "        end = [0 for _ in range(n + 1)]\n",
    "        id = 0\n",
    "\n",
    "        for l in leadership:\n",
    "            g[l[0]].append(l[1])\n",
    "        \n",
    "        # 深搜\n",
    "        def dfs(cur):\n",
    "            nonlocal id\n",
    "            id += 1\n",
    "            begin[cur] = id\n",
    "            for child in g[cur]:\n",
    "                dfs(child)\n",
    "            end[cur] = id\n",
    "        dfs(1)\n",
    "\n",
    "        ans = []\n",
    "        for o in operations:\n",
    "            if o[0] == 1:\n",
    "                seg.update(begin[o[1]], begin[o[1]], o[2])\n",
    "            if o[0] == 2:\n",
    "                seg.update(begin[o[1]], end[o[1]], o[2])\n",
    "            if o[0] == 3:\n",
    "                ans.append(seg.query(begin[o[1]], end[o[1]])%1000000007)\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node(object): #线段树\n",
    "\tdef __init__(self, lid = 0, rid = 0):\n",
    "\t\tself.val = 0\n",
    "\t\tself.delay = 0\n",
    "\t\tself.lid = lid\n",
    "\t\tself.rid = rid\n",
    "\t\tself.left = None\n",
    "\t\tself.right = None\n",
    "\n",
    "class Solution:\n",
    "\tdef bonus(self, n, leadership, operations):\n",
    "\t\tself.base = 10 ** 9 + 7\n",
    "\t\t#重新编号, 使每次操作针对连续区间, [left[i], i]表示i及其所有下属\n",
    "\t\tself.id = 0\n",
    "\t\tself.loc = [-1] * (n + 1) #原编号->新编号\n",
    "\t\tself.left = [-1] * (n + 1) #原编号->管辖区间左端点\n",
    "\t\tmap0 = [[] for _ in range(n + 1)]\n",
    "\t\tfor p, i in leadership:\n",
    "\t\t\tmap0[p].append(i)\n",
    "\t\tself.dfs(map0, 1)\n",
    "\t\troot = self.build(0, n - 1)\n",
    "\t\tans = []\n",
    "\t\tfor op in operations:\n",
    "\t\t\tl = self.left[op[1]]\n",
    "\t\t\tr = self.loc[op[1]]\n",
    "\t\t\tif op[0] == 1:\n",
    "\t\t\t\tself.update(root, r, r, op[2])\n",
    "\t\t\telif op[0] == 2:\n",
    "\t\t\t\tself.update(root, l, r, op[2])\n",
    "\t\t\telse:\n",
    "\t\t\t\tans.append(self.query(root, l, r))\n",
    "\t\treturn ans\n",
    "\t\n",
    "\tdef dfs(self, map0, cur):\n",
    "\t\tleft = -1\n",
    "\t\tfor v in map0[cur]:\n",
    "\t\t\ttmp = self.dfs(map0, v)\n",
    "\t\t\tif left == -1:\n",
    "\t\t\t\tleft = tmp\n",
    "\t\tself.loc[cur] = self.id\n",
    "\t\tself.id += 1\n",
    "\t\tself.left[cur] = self.loc[cur] if left == -1 else left\n",
    "\t\treturn self.left[cur]\n",
    "\t\n",
    "\tdef build(self, l, r): #建立线段树\n",
    "\t\tif l == r:\n",
    "\t\t\treturn Node(l, r)\n",
    "\t\troot = Node(l, r)\n",
    "\t\tm = (l + r) >> 1\n",
    "\t\troot.left = self.build(l, m)\n",
    "\t\troot.right = self.build(m + 1, r)\n",
    "\t\treturn root\n",
    "\t\n",
    "\tdef update(self, root, l1, r1, add):\n",
    "\t\tl = root.lid\n",
    "\t\tr = root.rid\n",
    "\t\tif r < l1 or l > r1: #当前区间和待更新区间无交集, 不处理\n",
    "\t\t\tpass\n",
    "\t\telif l1 <= l and r <= r1: #当前区间包含于待更新区间, 懒操作\n",
    "\t\t\troot.val = (root.val + add * (r - l + 1)) % self.base #val包含delay部分\n",
    "\t\t\troot.delay = (root.delay + add) % self.base\n",
    "\t\telse:\n",
    "\t\t\tif root.delay != 0:\n",
    "\t\t\t\tself.update(root.left, root.left.lid, root.left.rid, root.delay)\n",
    "\t\t\t\tself.update(root.right, root.right.lid, root.right.rid, root.delay)\n",
    "\t\t\t\troot.delay = 0\n",
    "\t\t\troot.val = (self.update(root.left, l1, r1, add) + self.update(root.right, l1, r1, add)) % self.base\n",
    "\t\treturn root.val\n",
    "\t\n",
    "\tdef query(self, root, l1, r1):\n",
    "\t\tl = root.lid\n",
    "\t\tr = root.rid\n",
    "\t\tif r < l1 or l > r1: #当前区间和查询区间无交集\n",
    "\t\t\treturn 0\n",
    "\t\tif l1 <= l and r <= r1: #当前区间包含于查询区间, 返回整个区间结果\n",
    "\t\t\treturn root.val\n",
    "\t\tif root.delay != 0: #delay下放\n",
    "\t\t\tself.update(root.left, root.left.lid, root.left.rid, root.delay)\n",
    "\t\t\tself.update(root.right, root.right.lid, root.right.rid, root.delay)\n",
    "\t\t\troot.delay = 0\n",
    "\t\treturn (self.query(root.left, l1, r1) + self.query(root.right, l1, r1)) % self.base"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bonus(self, n: int, leadership: List[List[int]], operations: List[List[int]]) -> List[int]:\n",
    "        mod = 10 ** 9 + 7\n",
    "        g = [[] for _ in range(n+1)]\n",
    "        for u, v in leadership:\n",
    "            g[u].append(v)\n",
    "        l = dict()\n",
    "        cnt = 0\n",
    "        def dfs(u):\n",
    "            nonlocal cnt\n",
    "            cnt += 1\n",
    "            start = cnt\n",
    "            for v in g[u]:\n",
    "                dfs(v)\n",
    "            end = cnt\n",
    "            l[u] = [start, end]\n",
    "        dfs(1)\n",
    "\n",
    "        L = 1\n",
    "        R = 50001\n",
    "        ans = []\n",
    "        root = SegTree().root\n",
    "        for op in operations:\n",
    "            if op[0] == 1:\n",
    "                t = l[op[1]]\n",
    "                SegTree.update(root, L, R, t[0], t[0], op[2])\n",
    "            elif op[0] == 2:\n",
    "                t = l[op[1]]\n",
    "                SegTree.update(root, L, R, t[0], t[1], op[2])\n",
    "            else:\n",
    "                t = l[op[1]]\n",
    "                ans.append(SegTree.query(root, L, R, t[0], t[1]) % mod)\n",
    "        return ans\n",
    "            \n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.left = self.right = None\n",
    "        self.val = self.lazy = 0\n",
    "\n",
    "class SegTree:\n",
    "    def __init__(self):\n",
    "         self.root = Node()\n",
    "\n",
    "    @staticmethod\n",
    "    def pushdown(root, L, R):\n",
    "        if root.left == None: root.left = Node()\n",
    "        if root.right == None: root.right = Node()\n",
    "        if root.lazy == 0: return\n",
    "        mid = (L + R) // 2\n",
    "        root.left.val += (mid - L + 1) * root.lazy\n",
    "        root.left.lazy += root.lazy\n",
    "        root.right.val += (R - mid) * root.lazy\n",
    "        root.right.lazy += root.lazy\n",
    "        root.lazy = 0\n",
    "\n",
    "    @staticmethod\n",
    "    def update(root, L, R, l, r, val):\n",
    "        if l <= L and R <= r:\n",
    "            root.val += (R - L + 1) * val\n",
    "            root.lazy += val\n",
    "            return\n",
    "        SegTree.pushdown(root, L, R)\n",
    "        mid = (L + R) // 2\n",
    "        if l <= mid: SegTree.update(root.left, L, mid, l, r, val)\n",
    "        if mid < r: SegTree.update(root.right, mid+1, R, l, r, val)\n",
    "        root.val = root.left.val + root.right.val\n",
    "\n",
    "    @staticmethod\n",
    "    def query(root, L, R, l, r):\n",
    "        if l <= L and R <= r:\n",
    "            return root.val\n",
    "        SegTree.pushdown(root, L, R)\n",
    "        ans = 0\n",
    "        mid = (L + R) // 2\n",
    "        if l <= mid: ans += SegTree.query(root.left, L, mid, l, r)\n",
    "        if mid < r: ans += SegTree.query(root.right, mid+1, R, l, r)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Node:\n",
    "    __slot__ = 'val', 'left', 'right', 'lazy', 'max'\n",
    "    def __init__(self, val=0, lazy=0, left=None, right=None) -> None:\n",
    "        self.val = val \n",
    "        self.left = left \n",
    "        self.right = right \n",
    "        self.lazy = lazy\n",
    "\n",
    "\n",
    "class SegTree:\n",
    "    def __init__(self, val=0, start=-10**9, end=10**9 ) -> None:\n",
    "        self.root = Node(val=val)\n",
    "        self.start = start\n",
    "        self.end = end \n",
    "      \n",
    "    def update(self, l, r, val):\n",
    "        def _update(start=self.start, end=self.end, node=self.root):\n",
    "            if not node:\n",
    "                node = self.root\n",
    "            if l <= start and end <= r:\n",
    "                node.val += (end - start + 1) * val\n",
    "                node.lazy += val\n",
    "                return \n",
    "            \n",
    "            mid = math.floor((start + end) / 2)\n",
    "            self.pushDown(node, mid - start + 1, end - mid)\n",
    "            if l <= mid:\n",
    "                _update(start, mid, node.left)\n",
    "            if r > mid:\n",
    "                _update(mid + 1, end, node.right)\n",
    "            self.pushUp(node)\n",
    "        _update()\n",
    "        \n",
    "\n",
    "    def query(self, l, r):\n",
    "        def _query(node=self.root, start=self.start, end=self.end): #max\n",
    "            if l <= start and end <= r:\n",
    "                return node.val\n",
    "            mid = math.floor((start + end) / 2) \n",
    "            ans = 0\n",
    "            self.pushDown(node, mid - start + 1, end - mid)\n",
    "            if l <= mid: \n",
    "                ans += _query(node.left, start, mid)\n",
    "            if r > mid: \n",
    "                ans += _query(node.right, mid + 1, end)\n",
    "            return ans \n",
    "\n",
    "        return _query()\n",
    "\n",
    "    def pushDown(self, node, leftNum, rightNum):\n",
    "        if node.left == None:\n",
    "            node.left = Node()\n",
    "        if node.right == None: \n",
    "            node.right = Node()\n",
    "        if node.lazy == 0:\n",
    "            return\n",
    "        node.left.val += node.lazy * leftNum\n",
    "        node.right.val += node.lazy * rightNum\n",
    "        # 对区间进行「加减」的更新操作，下推懒惰标记时需要累加起来，不能直接覆盖\n",
    "        node.left.lazy += node.lazy\n",
    "        node.right.lazy += node.lazy\n",
    "\n",
    "        node.lazy = 0\n",
    "\n",
    "    def pushUp(self, node):\n",
    "        node.val = node.left.val + node.right.val\n",
    "  \n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def bonus(self, n: int, leadership: List[List[int]], operations: List[List[int]]):\n",
    "        seg = SegTree(0, 1, n)\n",
    "        g = defaultdict(lambda: [])\n",
    "        for leader, stuff in leadership:\n",
    "            g[leader].append(stuff)\n",
    "        \n",
    "        id = {}\n",
    "        k = 1\n",
    "        sum = defaultdict(lambda: 0)\n",
    "        def build(i):\n",
    "            nonlocal k, id\n",
    "            s = 1\n",
    "            id[i] = k \n",
    "            k += 1\n",
    "            for x in g[i]:\n",
    "                s += build(x)\n",
    "            sum[i] = s \n",
    "            return s\n",
    "\n",
    "        build(1)\n",
    "        ans = []\n",
    "        for o in operations:\n",
    "            if o[0] == 1:\n",
    "                seg.update(id[o[1]], id[o[1]], o[2])\n",
    "            if o[0] == 2:\n",
    "                seg.update(id[o[1]], id[o[1]]+sum[o[1]]-1, o[2])\n",
    "            if o[0] == 3:\n",
    "                ans.append(seg.query(id[o[1]], id[o[1]]+sum[o[1]]-1)%1000000007)\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Node:\n",
    "    __slot__ = 'val', 'left', 'right', 'lazy', 'max'\n",
    "    def __init__(self, val=0, lazy=0, left=None, right=None) -> None:\n",
    "        self.val = val \n",
    "        self.left = left \n",
    "        self.right = right \n",
    "        self.lazy = lazy\n",
    "\n",
    "\n",
    "class SegTree:\n",
    "    def __init__(self, val=0, start=-10**9, end=10**9 ) -> None:\n",
    "        self.root = Node(val=val)\n",
    "        self.start = start\n",
    "        self.end = end \n",
    "      \n",
    "    def update(self, l, r, val):\n",
    "        def _update(start=self.start, end=self.end, node=self.root):\n",
    "            if not node:\n",
    "                node = self.root\n",
    "            if l <= start and end <= r:\n",
    "                node.val += (end - start + 1) * val\n",
    "                node.lazy += val\n",
    "                return \n",
    "            \n",
    "            mid = math.floor((start + end) / 2)\n",
    "            self.pushDown(node, mid - start + 1, end - mid)\n",
    "            if l <= mid:\n",
    "                _update(start, mid, node.left)\n",
    "            if r > mid:\n",
    "                _update(mid + 1, end, node.right)\n",
    "            self.pushUp(node)\n",
    "        _update()\n",
    "        \n",
    "\n",
    "    def query(self, l, r):\n",
    "        def _query(node=self.root, start=self.start, end=self.end): #max\n",
    "            if l <= start and end <= r:\n",
    "                return node.val\n",
    "            mid = math.floor((start + end) / 2) \n",
    "            ans = 0\n",
    "            self.pushDown(node, mid - start + 1, end - mid)\n",
    "            if l <= mid: \n",
    "                ans += _query(node.left, start, mid)\n",
    "            if r > mid: \n",
    "                ans += _query(node.right, mid + 1, end)\n",
    "            return ans \n",
    "\n",
    "        return _query()\n",
    "\n",
    "    def pushDown(self, node, leftNum, rightNum):\n",
    "        if node.left == None:\n",
    "            node.left = Node()\n",
    "        if node.right == None: \n",
    "            node.right = Node()\n",
    "        if node.lazy == 0:\n",
    "            return\n",
    "        node.left.val += node.lazy * leftNum\n",
    "        node.right.val += node.lazy * rightNum\n",
    "        # 对区间进行「加减」的更新操作，下推懒惰标记时需要累加起来，不能直接覆盖\n",
    "        node.left.lazy += node.lazy\n",
    "        node.right.lazy += node.lazy\n",
    "\n",
    "        node.lazy = 0\n",
    "\n",
    "    def pushUp(self, node):\n",
    "        node.val = node.left.val + node.right.val\n",
    "  \n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def bonus(self, n: int, leadership: List[List[int]], operations: List[List[int]]):\n",
    "        seg = SegTree(0, 1, n)\n",
    "        g = defaultdict(lambda: [])\n",
    "        for leader, stuff in leadership:\n",
    "            g[leader].append(stuff)\n",
    "        \n",
    "        id = {}\n",
    "        k = 1\n",
    "        sum = defaultdict(lambda: 0)\n",
    "        def build(i):\n",
    "            nonlocal k, id\n",
    "            s = 1\n",
    "            id[i] = k \n",
    "            k += 1\n",
    "            for x in g[i]:\n",
    "                s += build(x)\n",
    "            sum[i] = s \n",
    "            return s\n",
    "\n",
    "        build(1)\n",
    "        ans = []\n",
    "        for o in operations:\n",
    "            if o[0] == 1:\n",
    "                seg.update(id[o[1]], id[o[1]], o[2])\n",
    "            if o[0] == 2:\n",
    "                seg.update(id[o[1]], id[o[1]]+sum[o[1]]-1, o[2])\n",
    "            if o[0] == 3:\n",
    "                ans.append(seg.query(id[o[1]], id[o[1]]+sum[o[1]]-1)%1000000007)\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bonus(self, n: int, leadership: List[List[int]], operations: List[List[int]]) -> List[int]:\n",
    "        children = collections.defaultdict(list)\n",
    "        for a, b in leadership:\n",
    "            children[a].append(b)\n",
    "        nodes = []\n",
    "        node_ranges = {}\n",
    "        def dfs(node):\n",
    "            nodes.append(node)\n",
    "            start = len(nodes)\n",
    "            for child in children[node]:\n",
    "                dfs(child)\n",
    "            end = len(nodes)\n",
    "            node_ranges[node] = (start, end)\n",
    "        dfs(1)\n",
    "\n",
    "        tree = Tree(1, n)\n",
    "        res = []\n",
    "        for op in operations:\n",
    "            rg = node_ranges[op[1]]\n",
    "            if op[0] == 1:\n",
    "                tree.update(rg[0], rg[0], op[2])\n",
    "            elif op[0] == 2:\n",
    "                tree.update(rg[0], rg[1], op[2])\n",
    "            else:\n",
    "                res.append(tree.query(rg[0], rg[1]) % 1000000007)\n",
    "        return res\n",
    "\n",
    "\n",
    "class Tree:\n",
    "    def __init__(self, l, r):\n",
    "        self.l = l\n",
    "        self.r = r\n",
    "        self.size = r - l + 1\n",
    "        self._left = None\n",
    "        self._right = None\n",
    "        self.mid = (l + r) // 2\n",
    "        self.lazy = 0\n",
    "        self.val = 0\n",
    "\n",
    "    @property\n",
    "    def left(self):\n",
    "        if self._left is None:\n",
    "            self._left = Tree(self.l, self.mid)\n",
    "        return self._left\n",
    "\n",
    "    @property\n",
    "    def right(self):\n",
    "        if self._right is None:\n",
    "            self._right = Tree(self.mid + 1, self.r)\n",
    "        return self._right\n",
    "\n",
    "    def update(self, l, r, val):\n",
    "        if l == self.l and r == self.r:\n",
    "            self.val += val * self.size\n",
    "            self.lazy += val\n",
    "            return\n",
    "        if self.lazy:\n",
    "            self.left.lazy += self.lazy\n",
    "            self.right.lazy += self.lazy\n",
    "            self.left.val += self.lazy * self.left.size\n",
    "            self.right.val += self.lazy * self.right.size\n",
    "            self.lazy = 0\n",
    "        if r <= self.mid:\n",
    "            self.left.update(l, r, val)\n",
    "        elif l >= self.mid + 1:\n",
    "            self.right.update(l, r, val)\n",
    "        else:\n",
    "            self.left.update(l, self.mid, val)\n",
    "            self.right.update(self.mid + 1, r, val)\n",
    "        self.val = self.left.val + self.right.val\n",
    "\n",
    "    def query(self, l, r):\n",
    "        if l == self.l and r == self.r:\n",
    "            return self.val\n",
    "        if self.lazy:\n",
    "            self.left.lazy += self.lazy\n",
    "            self.right.lazy += self.lazy\n",
    "            self.left.val += self.lazy * self.left.size\n",
    "            self.right.val += self.lazy * self.right.size\n",
    "            self.lazy = 0\n",
    "        if r <= self.mid:\n",
    "            return self.left.query(l, r)\n",
    "        elif l >= self.mid + 1:\n",
    "            return self.right.query(l, r)\n",
    "        else:\n",
    "            return (\n",
    "                self.left.query(l, self.mid) +\n",
    "                self.right.query(self.mid + 1, r)\n",
    "            )\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
